import java.util.*;

/**
 * @author LKQ
 * @date 2022/6/16 10:32
 * @description 回溯，每次从四个数里面选择两个计算加减乘除，然后变3个数，在从三个里面挑选两个。。。
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] cards = {4, 1, 8, 7};
        solution.judgePoint24(cards);
    }
    static final int target = 24;
    /**
     * 精度
     */
    static final double epsilon = 1e-6;
    static final int add = 0, multiply = 1, subtract = 2, divide = 3;
    public boolean judgePoint24(int[] cards) {
        List<Double> list = new ArrayList<>();
        // 将数字转为double类型，因为除法为实数除法
        for (int num : cards) {
            list.add((double) num);
        }
        return solve(list);
    }
    public boolean solve(List<Double> list) {
        if (list.size() == 0) {
            return false;
        }
        if (list.size() == 1) {
            // 列表最后只剩一个数字, 判断两者之差是否在精度范围内
            return Math.abs(list.get(0) - target) < epsilon;
        }
        int size = list.size();
        // 从 list 选择 a
        for (int i = 0; i < size; i++) {
            // 从 list 选择b
            for (int j = 0; j < size; j++) {
                if (i != j) {
                    // 不能重复挑选
                    List<Double> newList = new ArrayList<>();
                    // 两个数做加减乘除运算
                    double a = list.get(i), b = list.get(j);
                    for (int k = 0; k < size; k++) {
                        if (k != i && k != j) {
                            // 将剩余的数加入新list中
                            newList.add(list.get(k));
                        }
                    }
                    // 对于四种运算
                    for (int k = 0; k < 4; k++) {
                        if (k < 2 && i > j) {
                            // 加法或乘法，满足交换律, 前面已经计算过，剪枝
                            continue;
                        }
                        if (k == add) {
                            newList.add(a + b);
                        }else if (k == multiply) {
                            newList.add(a * b);
                        }else if (k == subtract) {
                            newList.add(a - b);
                        }else if (k == divide) {
                            if (Math.abs(b) < epsilon) {
                                // 如果除数接近0
                                continue;
                            }else {
                                newList.add(a / b);
                            }
                        }
                        if (solve(newList)) {
                            return true;
                        }
                        // 回溯失败，那么删除运算的结果
                        newList.remove(newList.size() - 1);
                    }
                }
            }
        }
        return false;
    }
}
